// 上台阶 三步 问题
public class Code2 {
    public int waysToStep(int n) {
        // 1、创建 dp 表
        // 2、初始化
        // 3、填表
        // 4、返回值

        int mod = (int)1e9 + 7;

        // 优先处理边界值情况
        if(n == 1||n == 2) return n;
        if(n == 3) return 4;

        // 这里要先创建出一个dp表
        int[] dp = new int[ n + 1 ];

        // 简单分析一下
        // 台阶1 ： 有 1 种走法
        // 台阶2 ： 自身 1 种 + 前面一台阶的走法
        // 台阶3 ： 自身 1 种 + 前面两台阶的全部走法
        // 台阶4 ： 自身 1 种 + 前面最多三阶的走法.....
        // 以此类推

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        //填表
        for(int i = 4; i <= n; i++){
            dp[i] = ((dp[i - 1] + dp[i - 2])%mod + dp[i - 3])%mod;
        }
        return dp[n];
    }
}
